% LaTeX source for the CACM submission version of the paper,
% ``Visualizing Evaluation in Applicative Languages''
% Copyright, David S. Touretzky and Peter Lee
% November, 1989

\documentstyle[twoside,12pt,cmu-titlepage,fullpage,evaltrace,code]{article}
\newcommand{\ie}{{\it i.e.}}
\newcommand{\eg}{{\it e.g.}}
\newcommand{\vs}{{\it vs.}}
\newcommand{\horizline}{{\noindent\rule{\textwidth}{.01in}}}

\makeatletter \@twosidetrue \makeatother   % works around a local bug
\pagestyle{myheadings}
\markboth{Visualizing Evaluation \hfil}{Visualizing Evaluation \hfil}

\oddsidemargin 15pt       % more bug workarounds
%\evensidemargin -15pt

\title{Visualizing Evaluation in\\ Applicative Languages}
\author{David S. Touretzky and Peter Lee}
\date{\today}
\trnumber{CMU-CS-89-198-R}

\support{This research was supported in part by the Office of Naval
Research under contract N00014-84-K-0415 and in part by the Defense
Advanced Research Projects Agency (DOD), ARPA Order No.~5404, monitored
by the Office of Naval Research under the same contract.}

\abstract{In this article we present a technique for visualizing
evaluation in applicative languages that helps to graphically explain
a number of basic concepts, including lexical \vs\ dynamic scoping,
closures, the nature of the EVAL/APPLY duality, local and special
variables, and macro expansion.  Called ``evaltrace notation,'' it
appears in a recent textbook by the first author and has been employed
in several courses at Carnegie Mellon.  Although our discussion
focuses primarily on the notation itself, we also provide some
insights into the implementation of Lisp and Scheme interpreters and
the differences between the lexical and dynamic scoping disciplines.
It is our hope that evaltrace notation will be widely adopted by Lisp
educators.  In support of this, we have made available a set of
\LaTeX\ macros to allow others to produce evaltrace diagrams similar
to the ones that appear here.}

\begin{document}

\maketitle
\evensidemargin -15pt

\section{Introduction}

The EVAL and APPLY operations form the core of a Lisp interpreter and are
fundamental to implementations of applicative languages in general.  One of
the more difficult tasks in teaching Lisp to beginners is getting them to
understand the true nature of the EVAL/APPLY duality.  With the advent of
Scheme \cite{R3Scheme} and Common Lisp \cite{CLtL}, even experienced Lisp
programmers may find that they don't fully understand evaluation, especially
as it relates to lexical \vs\ dynamic scoping, closures, local and special
variables, and macro expansion.

In this article we present a technique for visualizing evaluation in
applicative languages that helps to graphically explain each of the above
concepts.  Called ``evaltrace notation,'' it appears in a recent textbook by
the first author \cite{TouretzkyLisp} and has been employed in several courses
at Carnegie Mellon.  Although our discussion in this paper focuses primarily
on the notation itself, we also provide some insights into the implementation
of Lisp and Scheme interpreters and the differences between the lexical and
dynamic scoping disciplines.  Extensions to other features such as
tail-recursion elimination and first-class continuations are quite easy to
make, though we do not include them here.  It is our hope that evaltrace
notation will be widely adopted by Lisp educators.  In support of this, we are
making available a set of \LaTeX\ macros to allow others to produce evaltrace
diagrams similar to the ones that appear here.

\section{The Basic Evaltrace Notation}

Evaluation in Lisp proceeds according to a set of evaluation rules built into
the EVAL and APPLY functions.  Evaluation of the simple expression \verb'(+ 2
3)' employs two of these rules.  First, numbers evaluate to themselves.
Second, to evaluate a list describing a function call, one first evaluates the
arguments to the function, and then {\it applies\/} the function to the
evaluated arguments.  This leads to the evaltrace of \verb'(+ 2 3)' shown
below.  Thin lines represent calls to EVAL, and thick lines calls to APPLY.

\begin{evaltrace}
+--> ;(++ 2 3)
|
|  +--> ;2                  {\it First argument evaluates to itself.}
|  |
|  +_-> ;2
|
|  +--> ;3                  {\it Second argument evaluates to itself.}
|  |
|  +_-> ;3
|
+**> ;Apply ++ to 2 and 3    {\it Apply the function to its arguments.}
*
+_*> ;5
\end{evaltrace}

Often we will want to suppress some details, such as the evaluation of trivial
arguments to a function, or the application of a primitive like \verb'+'\@.
In that case, the above evaluation is depicted this way:

\begin{evaltrace}
+--> ;(++ 2 3)
|
+_-> ;5
\end{evaltrace}

When an evaltrace diagram is elided like this to a single application of EVAL,
it is equivalent to the simple evaluation arrow used in \cite{CLtL} and most
other books on Lisp:

\begin{code}
(+ 2 3) {\et -->} 5
\end{code}

The real power of evaltrace notation becomes apparent when we consider the
application of non-primitive functions, since these may create local variables
and call other functions from within their bodies.  The function DOUBLE below
creates a local variable N to hold its argument, and calls the primitive
function \verb'*' to compute its result.  (All of the examples in this paper
are written in Common Lisp.)

\begin{code}
(defun double (n)
  (* n 2))
\end{code}

\noindent An evaltrace of the expression \verb'(double (+ 3 5))' shows how
a local variable is created inside the body of DOUBLE to hold the evaluated
argument.

\begin{evaltrace}
+--> ;(double (++ 3 5))
|
|  +--> ;(++ 3 5)
|  |
|  +_-> ;8
|
+**> ;Apply DOUBLE to 8
*    ;create local variable N with value 8
*
*  +--> ;(* n 2)
*  | "n"-->"8"
*  | "2"-->"2"
*  +_-> ;16
+_*> ;Result of DOUBLE is 16
\end{evaltrace}

This example involves the evaluation of the symbol N\@.  The evaluation rule
for symbols is that they evaluate to the value of the variable which they
name.  In earlier Lisp dialects people would speak of symbols themselves being
variables or having values, but this is not appropriate in Scheme or Common
Lisp since several variables with the same name may exist simultaneously in
different lexical contexts.  The symbol N appearing in the body of DOUBLE
refers to the local variable N that is created when DOUBLE is applied.
Outside the body of DOUBLE, the symbol N does not refer to this variable.  The
fact that this is a {\em textual\/} property of the program is important, as
it means that illegal references to N can easily be caught by a compiler,
before calls to DOUBLE are actually evaluated.

When DOUBLE is applied, a {\it lexical contour\/} is created in which
the variable named N resides.  In the evaltrace diagram, the thick line
marking the application of DOUBLE shows the boundaries of this lexical
contour.  Only thick lines denote lexical contours.  Thin lines, which
represent calls to EVAL, do not denote contours.  This distinction is an
important part of the scoping of Lisp programs, which will be discussed
later.  

It is easy to forget that lexical contours are created only when a function is
applied, not when it is defined.  If DOUBLE were to be applied five times,
five distinct lexical contours, each with its own variable named N, would be
created.  Consider the following function:

\begin{code}
(defun quintuple (n)
  (+ (double (double n)) n))
\end{code}

\begin{figure}
\horizline

\begin{evaltrace}
+--> ;(quintuple 5)
|
+**> ;Apply QUINTUPLE to 5
*    ;create local variable N with value 5
*                                          ;{\it QUINTUPLE\/'s variable N has value 5}
*  +--> ;(++ (double (double n)) n)
*  |  +--> ;(double (double n))
*  |  |  +--> ;(double n)
*  |  |  |  "n"-->"5"
*  |  |  +**> ;Apply DOUBLE to 5
*  |  |  *    ;create local variable N with value 5
*  |  |  *
*  |  |  *  +--> ;(* n 2)
*  |  |  *  | "n"-->"5"
*  |  |  *  +_-> ;10
*  |  |  +_*> ;Result of DOUBLE is 10
*  |  +**> ;Apply DOUBLE to 10
*  |  *    ;create local variable N with value 10
*  |  *
*  |  *  +--> ;(* n 2)
*  |  *  | "n"-->"10"
*  |  *  +_-> ;20
*  |  +_*> ;Result of DOUBLE is 20
*  |
*  | "n"-->"5"                             ;{\it QUINTUPLE\/'s variable N is still 5}
*  |
*  +**> ;Apply ++ to 20 and 5
*  *
*  +_*> ;Result of ++ is 25
+_*> ;Result of QUINTUPLE is 25
\end{evaltrace}

 \caption{Evaltrace diagram illustrating the creation of contours.}
 \label{quintuple}

\horizline
\end{figure}

\noindent Both DOUBLE and QUINTUPLE, when applied, create local
variables named N\@.  Because of lexical scoping, QUINTUPLE's N is
distinct from DOUBLE's N\@.  Furthermore, each of the two applications
of DOUBLE creates a {\em new\/} variable referred to by the name N\@.
This can be seen in the evaltrace diagram given in
Figure~\ref{quintuple}, where three distinct lexical contours are
shown (not counting the one for \verb'+'), each containing a variable
named N\@.  These variables are independent.  Thus, the value of N in
QUINTUPLE's contour remains 5, even after the second call to DOUBLE
assigns the value 10 to a (distinct) variable which is also named N.

Every lexical contour has a {\em parent contour}, except that global variables
exist in a top-level contour (also called the {\em global contour\/}) that has
no parent.  Consider the function CIRCUMFERENCE that references a global
variable CRUDE-PI: (SETF is the general assignment operator in
Common Lisp.)

\begin{code}
(setf crude-pi 3.14)
\strut
(defun circumference (r)
  (* 2 r crude-pi))
\end{code}

\begin{evaltrace}
+--> ;(circumference 5)
|
+**> ;Apply CIRCUMFERENCE to 5
*    ;create local variable R with value 5
*
*  +--> ;(* 2 r crude-pi)
*  | "2"-->"2"
*  | "r"-->"5"
*  | "crude-pi"-->"3.14"
*  +_-> ;31.4
+_*> ;Result of CIRCUMFERENCE is 31.4
\end{evaltrace}

The rules for mapping symbols to the variables which they name are called
{\it scope rules.} When evaluating the symbol R in the body of
CIRCUMFERENCE, the first scope rule tells us to look in the current lexical
contour for a variable with that name.  Since there is a local variable
named R created by CIRCUMFERENCE, the symbol R is treated as a reference to
that variable.  But in the case of CRUDE-PI, there is no local variable by
that name in the current contour.  Consequently, the rules for lexical
scoping tell us to look in the parent contour, which happens to be the
global contour (which is also the only other contour in this example).  A
variable named CRUDE-PI does exist in the global contour, so the symbol
CRUDE-PI is taken to refer to that variable.

The difference between lexical and dynamic scoping disciplines is in the
way parent contours are determined.  We will return to this topic shortly.

\section{Nested Lexical Contours}

Within the body of a function, additional local variables may be created
using the LET special function.  Consider the following:

\begin{code}
(defun average (x y)
  (let ((sum (+ x y)))
    (list x y 'average (/ sum 2))))
\end{code}

\begin{figure}
\horizline

\begin{evaltrace}
+--> ;(average 3 7)
|
+**> ;Apply AVERAGE to 3 and 7
*    ;create local variable X with value 3
*    ;create local variable Y with value 7
*
*  +--> ;(let ((sum ...)) ...)
*  |   +--> ;(++ x y)
*  |   |
*  |   +_-> ;10
*  +%%> ;Enter LET body
*  %    ;create local variable SUM with value 10
*  %
*  %  +--> ;(list x y 'average (/ sum 2))
*  %  | "x"-->"3"
*  %  | "y"-->"7"
*  %  | "'average"-->"AVERAGE"
*  %  |  +--> ;(/ sum 2)
*  %  |  | "sum"-->"10"
*  %  |  +_-> ;5
*  %  +_-> ;(3 7 average 5)
*  +_%> ;(3 7 average 5)
+_*> ;Result of AVERAGE is (3 7 AVERAGE 5)
\end{evaltrace}

 \caption{Evaltrace diagram showing a local contour.}
 \label{average}

\horizline
\end{figure}

\noindent An evaltrace diagram for AVERAGE is shown in
Figure~\ref{average}\@. Notice that the lexical contour associated
with the LET body is drawn as a hollow arrow rather than a solid
arrow.  A solid arrow indicates that the parent contour is the global
contour.  The hollow arrow in this diagram indicates that the parent
contour is the immediately enclosing contour.  Thus the parent contour
of the LET body is the contour generated by the body of AVERAGE\@.
AVERAGE's parent contour is the global contour.  When evaluating the
symbol SUM inside the LET body, we find that there is a variable by
that name in the current contour.  But when evaluating X and Y in the
LET body, we find we must go look in the parent contour.  Since there
are local variables named X and Y in the contour of AVERAGE, the
symbols X and Y are taken to refer to those variables.  (This example
also illustrates another of Lisp's evaluation rules: quoted objects
evaluate to themselves, without the quote.)

Now we can present an example that highlights the distinction between lexical
and dynamic scoping.  Notice below that there is both a global variable N with
value 1000, and a local variable N in the argument list of PARENT\@.  PARENT
calls CHILD, which contains the symbol N in its body.  To which variable does
CHILD's N refer?

\begin{code}
(setf n 1000)
\strut
(defun parent (n)
  (child (+ n 2)))
\strut
(defun child (p)
  (list n p))
\end{code}

Under lexical scoping, every function has associated with it, as part of its
definition, a parent contour.  Functions defined at the top level with DEFUN
always have the global contour as their parent.  (We'll have more to say later
about how contours are associated with functions that are not defined at the
top level\@.)  A function's {\em environment\/} is the set of objects visible
within its contour, in other words, objects that reside in its own contour, or
in its parent contour, or in its parent contour's parent contour, and so on.
Functions can only access those variables that are visible within their
environment.  Variables that have the same name ``shadow'' each other.  For
instance, a variable N in the current contour would shadow a variable N in the
parent contour, so the latter would not be visible.

In evaltrace diagrams, environments are depicted graphically via the chain
of nested contours that define them.  Most contours drawn with a hollow arrow
(such as LET contours) have the immediately surrounding contour as their
parent, while contours for functions defined at top level are drawn with a
solid arrow, indicating that their parent contour is the global contour.

\begin{figure}
\horizline

\begin{evaltrace}
;{\it the global variable N has value 1000}
\strut
+--> ;(parent 3)
|
+**> ;Apply PARENT to 3
*    ;create local variable N with value 3
*
*  +--> ;(child (++ n 2))
*  |  +--> ;(++ n 2)
*  |  | "n"-->"3"                 ;{\it Refer to PARENT's local N.}
*  |  +_-> ;5
*  |
*  +**> ;Apply CHILD to 5
*  *    ;create local variable P with value 5
*  *
*  *  +--> ;(list n p)
*  *  | "n"-->"1000"              ;{\it Refer to the global N.}
*  *  | "p"-->"5"
*  *  +_-> ;(1000 5)
*  +_*> ;Result of CHILD is (1000 5)
+_*> ;Result of PARENT is (1000 5)
\end{evaltrace}

 \caption{Evaltrace diagram illustrating lexical scoping.}
 \label{lexical}

\horizline
\end{figure}

Getting back to our present example, the lexical scope rules dictate
that the symbol N inside the body of CHILD must refer to the global
variable N, not to PARENT's local N.  This is illustrated by the
evaltrace diagram in Figure~\ref{lexical}\@.  CHILD's environment
consists of its own contour (in which the variable P resides), and its
parent contour, which is the global contour.  Since CHILD doesn't have
a local variable named N, the symbol N in its body must refer to the
global N, whose value is 1000.  PARENT's local variable N is
completely invisible to CHILD, since PARENT's contour is not part of
CHILD's environment.

This scheme is called {\em lexical\/} scoping because environments mirror
the nesting structure of the code.  Since CHILD isn't defined inside of
PARENT, none of PARENT's local variables are visible to it.  We'll say more
about the relationship between textual nesting and environments in the next
section.

Early Lisp dialects, from Lisp 1.5 up through MacLisp and InterLisp---and APL
and SNOBOL as well---use dynamic rather than lexical scoping
\cite{GabrielHistory}.  In dynamic scoping functions do not have parent
contours permanently associated with them; instead each contour
uses the most recently created contour as its parent.  Thus, environments are
determined dynamically rather than statically.  If the preceding example were
tried in a dynamically scoped Lisp, the parent contour of CHILD would be the
one created by PARENT, and the result of the evaluation would be different, as
shown in Figure~\ref{dynamic}.

\begin{figure}
\horizline

\begin{evaltrace}
;{\it the global variable N has value 1000}
\strut
+--> ;(parent 3)
|
+%%> ;Apply PARENT to 3
%    ;create variable N with value 3
%
%  +--> ;(child (++ n 2))
%  |  +--> ;(++ n 2)
%  |  |                             ;{\it Refer to PARENT's N.}
%  |  +_-> ;5
%  +%%> ;Apply CHILD to 5
%  %    ;create variable P with value 5
%  %
%  %  +--> ;(list n p)
%  %  |  "n"-->"3"                  ;{\it Refer to PARENT's N.}
%  %  |  "p"-->"5"
%  %  +_-> ;(3 5)
%  +_%> ;(3 5)
+_%> ;(3 5)
\end{evaltrace}

 \caption{Evaltrace diagram illustrating dynamic scoping.}
 \label{dynamic}

\horizline
\end{figure}

Dynamic scoping was used in early Lisp dialects because in an interpreter it
is the most straightforward scoping discipline to implement efficiently.
(This turns out not to be the case when compiling.  This is one reason that
modern dialects of Lisp which are compiled as well as interpreted, such as
Common Lisp, are lexically scoped.)  In evaltrace diagrams, the nesting of
contours accurately reflects the structure of the call stack of an
interpreter, with the inner-most contour being the top of the stack and the
global contour at the bottom.  So, we will often refer to the nesting of
contours as the call stack.  Dynamic scoping allows the call stack to be used
as the environment, which means that the contours in evaltrace diagrams are
drawn only with hollow, never solid, arrows.

\section{Scoping and Textual Inclusion}

Earlier we saw that the contours created by the LET special function are
drawn with hollow instead of solid arrows.  This is because LET creates
contours that are local to other contours.  In order to explain this
further, let's examine the LET function in more detail.

LET can be used to create any number of variables, with the property that the
creation of the variables and assignment of values to them is carried out ``in
parallel\@.''  The following (slightly unusual) definition of a function for
computing the greatest common divisor of two integers demonstrates a use of
this parallel feature.

\begin{code}
(defun gcd (x y)
  (if (= x y)
      x
      (let ((x (if (< x y) x y))
            (y (if (< x y) y x)))
        (gcd x (- y x)))))
\end{code}

\noindent The LET expression in GCD is used to ensure that X is less than Y,
swapping their values if necessary, before evaluating the recursive call in
the body.  Doing the swap correctly depends on the parallel nature of LET, as
the evaltrace given in Figure~\ref{gcd} shows.

\begin{figure}
\horizline

\begin{evaltrace}
+--> ;(gcd 12 6)
|
+**> ;Apply GCD to 12 and 6
*    ;create local variable X with value 12
*    ;create local variable Y with value 6
*  +--> ;(if (= x y) ...)
*  | "(= x y)"-->"NIL"
*  |  +--> ;(let ...)
*  |  |  +--> ;(if (< x y) x y)
*  |  |  | "(< x y)"-->"NIL"
*  |  |  | "y"-->"6"
*  |  |  +_-> ;6
*  |  |  +--> ;(if (< x y) y x)
*  |  |  | "(< x y)"-->"NIL"
*  |  |  | "x"-->"12"
*  |  |  +_-> ;12
*  |  +%%> ;Enter LET body
*  |  %    ;create local variable X with value 6
*  |  %    ;create local variable Y with value 12
*  |  %  +--> ;(gcd x (- y x))
*  |  %  | "X"-->"6"
*  |  %  | "(- y x)"-->"6"
*  |  %  +**> ;Apply GCD to 6 and 6
*  |  %  *    ;create local variable X with value 6
*  |  %  *    ;create local variable Y with value 6
*  |  %  *  +--> ;(if (= x y) ...)
*  |  %  *  | "(= x y)"-->"T"
*  |  %  *  | "X"-->"6"
*  |  %  *  +_-> ;6
*  |  %  +_*> ;Result of GCD is 6
*  |  +_%> ;6
*  +_-> ;6
+_*> ;Result of GCD is 6
\end{evaltrace}

 \caption{Evaltrace diagram illustrating LET.}
 \label{gcd}

\horizline
\end{figure}

The form of evaltrace diagrams for LET expressions exposes the fact
that the expressions \verb|(if (< x y) |$\ldots$\verb| )| are evaluated in a
context that cannot possibly be affected by the ``new'' versions of the
variables X and Y created in the LET body.  Therefore, these variables are
effectively created and assigned in ``parallel\@.''

Recall from before that the hollow arrow drawn for the LET body's contour
indicates that its parent is the immediately enclosing contour.  This nesting
of contours (\ie, the child-to-parent relationships between contours) is
completely determined by the textual inclusion of LET bodies in functions.  In
the above example, the parent for the local contour created by the LET
expression is GCD's contour because GCD textually includes the LET expression.
This is, in fact, a general rule for lexical scoping in Lisp: a contour $A$
can be the parent of another contour $B$ only if the Lisp code corresponding
to contour $A$ textually includes the code for $B$.

This all implies, also, that a function's environment always mirrors the
textual inclusions in the code.  This fact is important for understanding
closures, which we discuss in the next section.

Getting back to our discussion of LET, it should be noted that this
parallel behavior of LET is not always what one desires when creating local
variables.  For example:

\begin{code}
(defun price-change (name old new)
  (let ((diff (- new old))
        (proportion (/ diff old))
        (percentage (* proportion 100.0)))
    (list name 'changed 'by percentage 'percent)))
\end{code}

\begin{figure}
\horizline

\begin{evaltrace}
+--> ;(price-change 'widgets 1.25 1.35)
|
+**> ;Apply PRICE-CHANGE to WIDGETS, 1.25 and 1.35
*    ;create local variable NAME with value WIDGETS
*    ;create local variable OLD with value 1.25
*    ;create local variable NEW with value 1.35
*  +--> ;(let ...)
*  |  +--> ;(- new old)
*  |  | "new"-->"1.35"
*  |  | "old"-->"1.25"
*  |  +_-> ;0.10
*  |
*  |  +--> ;(/ diff old)
*  |  |
A_]a->+_-> ;Error!  DIFF unassigned variable.
\end{evaltrace}

 \caption{Evaltrace illustrating an incorrect use of LET.}
 \label{badlet}

\horizline
\end{figure}

\noindent Calling this function leads to an error, as illustrated by
the evaltrace in Figure~\ref{badlet}\@.  The value of DIFF is needed
in order to compute the value for PROPORTION, but the local variable
DIFF has not yet been created.  Therefore the reference to DIFF is
interpreted incorrectly as a reference to a global variable by that
name.  The global variable DIFF has not been assigned a value (or one
might say it doesn't exist), hence the error message.  The problem can
be remedied by carrying out the creation and assignment of the three
local variables serially, using the LET* special function in place of
LET.

\begin{code}
(defun price-change (name old new)
  (let* ((diff (- new old))
         (proportion (/ diff old))
         (percentage (* proportion 100.0)))
    (list name 'changed 'by percentage 'percent)))
\end{code}

\begin{figure}
\horizline

\begin{evaltrace}
+--> ;(price-change 'widgets 1.25 1.35)
|
+**> ;Apply PRICE-CHANGE to 1.25 and 1.35
*    ;create local variable NAME with value WIDGETS
*    ;create local variable OLD with value 1.25
*    ;create local variable NEW with value 1.35
*  +--> ;(let* ...)
*  |  +--> ;(- new old)
*  |  |
*  |  +_-> ;0.10
*  +%%> ;Enter LET body
*  %    ;create local variable DIFF with value 0.10
*  %  +--> ;(/ diff old)
*  %  |
*  %  +_-> ;0.08
*  %  +==> ;Enter LET body
*  %  %    ;create local variable PROPORTION with value 0.08
*  %  %  +--> ;(* proportion 100.0)
*  %  %  |
*  %  %  +_-> ;8.0
*  %  %  +==> ;Enter LET body
*  %  %  %    ;create local variable PERCENTAGE with value 8.0
*  %  %  %  +--> ;(list name 'changed 'by percentage 'percent)
*  %  %  %  |
*  %  %  %  +_-> ;(WIDGETS CHANGED BY 8.0 PERCENT)
*  D=!D=!+_%> ;(WIDGETS CHANGED BY 8.0 PERCENT)
+_*> ;Result of PRICE-CHANGE is (WIDGETS CHANGED BY 8.0 PERCENT)
\end{evaltrace}

 \caption{Evaltrace diagram illustrating LET*.}
 \label{price}

\horizline
\end{figure}

\noindent The evaltrace for this in Figure~\ref{price} shows that LET*
generates a new, nested contour for each variable it creates.  The
diagram suggests that LET* expressions behave like nested LET
expressions.

\section{Closures}

 In Lisp, functions are first-class data objects: they can be created on the
fly, passed as arguments, and returned as values.  Function objects are
created in Common Lisp by passing a lambda expression to the special function
FUNCTION\@.\footnote{In Scheme, LAMBDA is itself a special function that
creates function objects, so there is no need for a FUNCTION function.  In
Common Lisp, FUNCTION is usually abbreviated {\tt \#'} just as QUOTE is
abbreviated {\tt '}.} The result of FUNCTION is a new function object whose
parent contour is the current contour, and whose parameter list and body are
taken from the lambda expression.  These function objects are also known as
{\em lexical closures}.  We will denote these function objects as
\verb|#<Lexical-closure A>|, \verb|#<Lexical-closure B>|, and so on.

One of the most common uses for lexical closures is as arguments to
applicative operators such as MAPCAR\@.  In the example below, ZERO-CENTER
takes a list of numbers as input and adjusts them so that their sum is zero
without changing any of the distances between pairs of individual elements.
It does this by subtracting the average of the list (computed by AVERAGE) from
each element.  ZERO-CENTER creates a function object (a lexical closure) to do
this subtraction, and passes it to MAPCAR so that it can be applied to each
element in succession.

\begin{code}
(defun average (seq)
  (/ (reduce \#'+ seq) (length seq)))
\strut
(defun zero-center (data)
  (let ((avg (average data)))
    (mapcar \#'(lambda (x) (- x avg)) data)))
\strut
(zero-center '(3 11 13)) {\et -->} (-6 2 4)
\end{code}

\begin{figure}
\horizline

\begin{evaltrace}
+--> ;(zero-center '(3 11 13))
|
+**> ;Apply ZERO-CENTER to (3 11 13)
*    ;create local variable DATA with value (3 11 13)
*  +--> ;(let ...)
*  | "(average data)"-->"9"
*  +%%> ;Enter LET body
*  %    ;create local variable AVG with value 9
*  %  +--> ;(mapcar #'(lambda (x) (- x avg)) data)
*  %  |  +--> ;#'(lambda (x) (- x avg))
*  %  |  |
*  %  |  +_-> ;#<Lexical-closure A>
*  %  | "data"-->"(3 11 13)"
*  %  +**> ;Apply MAPCAR to #<Lexical-closure A> and (3 11 13)
*  %  *
*  %  *  +==> ;Apply #<Lexical-closure A> to 3
*  %  *  %    ;create local variable X with value 3
*  %<----/  +--> ;(- x avg)
*  %  *  %  |
*  %  *  %  +_-> ;-6
*  %  *  +_%> ;-6
*  %  *
*  %  *  +==> ;Apply #<Lexical-closure A> to 11
*  %  *  %    ;create local variable X with value 11
*  %<----/  +--> ;(- x avg)
*  %  *  %  |
*  %  *  %  +_-> ;2
*  %  *  +_%> ;2
*  %  *
*  %  *  +==> ;Apply #<Lexical-closure A> to 13
*  %  *  %    ;create local variable X with value 13
*  %<----/  +--> ;(- x avg)
*  %  *  %  |
*  %  *  %  +_-> ;4
*  %  *  +_%> ;4
*  %  +_*> ;Result of MAPCAR is (-6 2 4)
*  +_%> ;(-6 2 4)
+_*> ;Result of ZERO-CENTER is (-6 2 4)
\end{evaltrace}

 \caption{Evaltrace diagram illustrating functional arguments.}
 \label{zero}

\horizline
\end{figure}

The function object passed to MAPCAR contains a reference to the variable AVG
in its body.  Therefore, it is important that the closure's parent contour be
the contour where the closure was created, not the global contour, in order
for the closure to be able to access ZERO-CENTER's local variable AVG.
This relationship is depicted in Figure~\ref{zero}.

Notice that MAPCAR's contour is interposed between the contour created by
the LET body and the contours for each invocation of \verb|#<|Lexical-closure
A\verb|>|\@.  MAPCAR's parent contour is the global contour.  But this doesn't
matter, because the closure doesn't find its parent by looking for the most
recently created contour (\ie, just below the top of the call stack)\@.  The
parent is determined at the time the closure is defined, and it is remembered
explicitly as part of the closure object itself.  In the evaltrace diagram,
each time the closure is invoked by MAPCAR, its parent contour is shown by a
leftward-pointing arrow that appears to ``jump over'' the MAPCAR contour to
point to the LET body where the closure was defined.  What's really happening
is that the closure is ``remembering'' that the LET body's contour is its
parent; it ignores the contour created by the invocation of MAPCAR.

This behavior is consistent with our textual-inclusion explanation.  The
text for the lambda expression that gave rise to the closure appears inside
the body of the LET, so the LET forms part of the closure's environment.
There is no reason for the closure to be able to access any of the local
variables of MAPCAR, since it does not appear within the body of the
definition of MAPCAR.

Functions created solely to be passed as arguments are known as {\em
funargs\/} in Lisp.  They have the property that their parent contour is
always somewhere below them on the call stack, although as in the preceding
example it will not be immediately below them.  Early Lisp dialects (as well
as many block-structured languages like Pascal and Ada) allowed function
objects to be used only as funargs: a function object could be passed to other
functions, but it could not be returned as a value by the function that
created it, because then its parent contour would no longer be on the call
stack.  In Scheme and Common Lisp this restriction has been eliminated; it is
possible for contours to remain in existence even after the function call that
created them has returned.  This is accomplished by locating the contour in
heap storage rather than on the stack, when necessary.  (Actually, real
implementations use many different strategies for representing contours in
memory.  As a conceptual device, however, it is useful to think in terms of
the representation of contours in the heap and stack\@.)  This means that we
need a special way to draw contours for functions that are returned as values.
Consider the function SHIFTER below, which {\em returns\/} a closure that
references SHIFTER's local variable KONST:

\begin{code}
(defun shifter (konst)
  \#'(lambda (x) (- x konst)))
\end{code}

\noindent Below we have rewritten the function ZERO-CENTER in order to
demonstrate the use of the closures returned by SHIFTER\@.  ZERO-CENTER calls
SHIFTER to create a closure that will subtract the average value from its
input.  It then uses MAPCAR to apply this closure to ZERO-CENTER's input
values, DATA.

\begin{code}
(defun zero-center (data)
  (mapcar (shifter (average data)) data))
\end{code}

\begin{figure}
\horizline

\begin{evaltrace}
                +--> ;(zero-center '(3 11 13))
                |
                +**> ;Apply ZERO-CENTER to (3 11 13)
                *    ;create local variable DATA with value (3 11 13)
                *  +--> ;(mapcar (shifter (average data)) data)
                *  |  +--> ;(shifter (average data))
                *  |  | "(average data)"-->"9"
                *  |  +**> ;Apply SHIFTER to 9
                *  |  *    ;create local variable KONST with value 9
                *  |  *  +--> ;#'(lambda (x) (- x konst))
      e..................'
      :         *  |  *  +_-> ;#<Lexical-closure A>
      v         *  |  +_*> ;Result of SHIFTER is #<Lexical-closure A>
q-----------w   *  | "data"-->"(3 11 13)"
|           |   *  +**> ;Apply MAPCAR to #<Lexical-closure A> and (3 11 13)
|"KONST = 9"|   *  *
|           |   *  *  +==> ;Apply #<Lexical-closure A> to 3
a-----------s   *  *  %    ;create local variable X with value 3
      ^         *  *  %  +--> ;(- x konst)
      |         *  *  %  |
      a---------------/  +_-> ;-6
      ^         *  *  +_%> ;-6
      |         *  *
      |         *  *  +==> ;Apply #<Lexical-closure A> to 11
      |         *  *  %    ;create local variable X with value 11
      |         *  *  %  +--> ;(- x konst)
      a---------------/  |
      ^         *  *  %  +_-> ;2
      |         *  *  +_%> ;2
      |         *  *
      |         *  *  +==> ;Apply #<Lexical-closure A> to 13
      |         *  *  %    ;create local variable X with value 13
      |         *  *  %  +--> ;(- x konst)
      a---------------/  |
                *  *  %  +_-> ;4
                *  *  +_%> ;4
                *  +_*> ;Result of MAPCAR is (-6 2 4)
                +_*> ;Result of ZERO-CENTER is (-6 2 4)
\end{evaltrace}

 \caption{Evaltrace diagram illustrating closures.}
 \label{closure}

\horizline
\end{figure}

\noindent When SHIFTER returns a lexical closure, its parent contour,
SHIFTER's contour, is preserved on the heap.  This is shown in the
evaltrace diagram in Figure~\ref{closure} as a box on the left in
which the local variables of the contour reside.  The local variable
KONST resides in this box.  When the closure is invoked within the
body of MAPCAR, its parent contour is this preserved contour.  Within
the body of the closure, the symbol X evaluates to its local value
because X is a local variable in the closure's contour; the symbol
KONST evaluates to 9 because there is a variable by that name visible
in the parent contour.

Just like other data objects that are allocated in the heap, the contour for
the lexical closure can be garbage collected when there are no longer any
pointers to it.

\section{Macro Expansion}

Macros provide a way to extend the syntax of Lisp.  A macro function is
applied to its {\em unevaluated} arguments.  Its parent contour is the global
contour.  The result returned by a macro function is a Lisp expression which
is then evaluated in the lexical context where the macro call appeared.  As
with the duality between EVAL and APPLY, it is often hard to teach beginners
how macros work, but evaltrace notation can be used to show macros in action.
Consider the SIMPLE-INCF macro, a simplified version of Common Lisp's INCF:

\begin{code}
(defmacro simple-incf (var)
  (print a)
  (list 'setq var (list '+ var 1)))
\strut
(setf a 'foo)
\strut
(defun test (a)
  (simple-incf a))
\end{code}

\begin{figure}
\horizline

\begin{evaltrace}
;{\it the global variable A has value FOO}
\strut
+--> ;(test 5)
|
+**> ;Apply TEST to 5
*    ;create local variable A with value 5
*  +..> ;(simple-incf a)
*  :  +__> ;Apply macro SIMPLE-INCF to A
*  :  *    ;create local variable VAR with value A
*  :  *  +--> ;(print a)
*  :  *  | "a"-->"FOO"
*  :  *  |      ;print FOO
*  :  *  +_-> ;FOO
*  :  *  +--> ;(list 'setq var (list '++ var 1))
*  :  *  |
*  :  *  +_-> ;(SETQ A (++ A 1))
*  :  +_*> ;Result of macro expansion is (SETQ A (++ A 1))
*  +.-> ;(setq a (++ a 1))
*  | "(++ a 1)"-->"6"
*  |     ;set local variable A to 6
*  +_-> ;6
+_*> ;Result of TEST is 6
\end{evaltrace}

 \caption{Evaltrace diagram illustrating macro expansion.}
 \label{macro}

\horizline
\end{figure}

An evaltrace of this macro is shown in Figure~\ref{macro}\@.  Note
that the symbol A appearing in the body of the macro is taken as a
reference to the global variable A, because the macro's parent contour
is the global contour.  But the A appearing in the SETQ expression
returned by the macro is evaluated within the lexical context of TEST,
and so refers to the local variable A visible in the body of TEST.

Macro expansions are drawn with a dotted line.  The result of a macro
expansion is evaluated normally, as shown by the thin solid line to which
the dotted line connects.  Notice that the argument to the macro is not
evaluated, so the input to SIMPLE-INCF is the symbol A instead of the value
5.

\section{Special Variables}

Variables in Common Lisp are lexically scoped by default, but it is still
possible to have a kind of dynamically scoped variable called a {\em
special variable}.  There is no special evaltrace notation for dynamic
variables; one simply notes whether a given name has been declared special
or not, and once it has, all variables with that name will be dynamically
scoped.  By convention, special variable names are written with surrounding
asterisks, so that they can be easily distinguished from lexical variable
names.  A variable name can be declared special with the DEFVAR form.
Let's return to our earlier PARENT/CHILD example, but this time with a
special variable.

\begin{code}
(defvar *n* 1000)
\strut
(defun parent (*n*)
  (child (+ *n* 2)))
\strut
(defun child (p)
  (list *n* p))
\end{code}

\begin{figure}
\horizline

\begin{evaltrace}
;{\it the top level dynamic variable *N* has value 1000}
\strut
+--> ;(parent 3)
|
+**> ;Apply PARENT to 3
*    ;create dynamic variable *N* with value 3
*
*  +--> ;(child (++ *n* 2))
*  |  +--> ;(++ *n* 2)
*  |  |
*  |  +_-> ;5
*  +**> ;Apply CHILD to 5
*  *    ;create local variable P with value 5
*  *
*  *   +--> ;(list *n* p)
*  *   | "*n*"-->"3"
*  *   | "p"-->"5"
*  *   +_-> ;(3 5)
*  +_*> ;Result of CHILD is (3 5)
+_*> ;Result of PARENT is (3 5)
\strut
;{\it *N* still has value 1000}
\end{evaltrace}

 \caption{Evaltrace diagram illustrating Common Lisp's ``special'' variables.}
 \label{dynscope}

\horizline
\end{figure}

An evaltrace of PARENT is given in Figure~\ref{dynscope}\@.  The
evaluation rule for dynamically scoped variables is that we search all
the enclosing contours in the order they appear on the call stack,
ignoring the contours' pointers to their normal (lexical) parents.
The top level dynamic value is used only if we make it all the way out
to the global contour, meaning that no other contour presently has a
variable with the same name.  PARENT ``rebinds'' the special variable
*N*, meaning that it establishes a (temporary) new dynamic variable
with the name *N* that lasts as long as PARENT remains on the call
stack.  Dynamic variables cannot be maintained in closures, since they
are entirely dependent on the call stack.  PARENT's binding of a
variable *N* with value 3 is in effect when CHILD evaluates *N*, so
that is the variable that CHILD sees.  When PARENT exits, its binding
of *N* disappears, and thus the previous binding of *N* becomes
visible again.

\section{Conclusion}

We think evaltrace notation is an effective tool for teaching the key concepts
of evaluation in Lisp and other applicative languages.  We also find that
evaltrace is flexible---extensions to other features of Lisp such as
tail-recursion elimination and first-class continuations (CALL/CC) are quite
easy to make, though we have not included them here.

Because tracing has been a part of Lisp since the days of Lisp 1.5, we
should point out how evaltrace diagrams differ from earlier tracing
schemes.  Lisp tracing programs usually work by replacing the body of
the function to be traced; thus they are only able to show the APPLY
part of the evaluation process.  This can lead to ambiguities.  For
example, for the the functions FOO1 and FOO2

\begin{code}
(defun bar (y) y)
\strut
(defun baz (z) z)
\strut
(defun foo1 (x)
  (bar (baz x)))
\strut
(defun foo2 (x)
  (baz x)
  (bar x))
\end{code}

\noindent identical traces are produced in most Lisp implementations,
as shown in Figure~\ref{ambig}.  In both cases, BAZ is invoked before
BAR.  But in the first case BAZ is computing the argument to BAR,
while in the second case the calls to BAZ and BAR are independent.
This difference is clearly portrayed in the corresponding evaltrace
diagrams given in Figure~\ref{eval}.

\begin{figure}
\horizline

\begin{code}
(trace bar baz foo1 foo2)
\strut
> (foo1 3)
 0: (FOO1 3)
   1: (BAZ 3)
   1: returned 3
   1: (BAR 3)
   1: returned 3
 0: returned 3
3
\strut
> (foo2 3)
 0: (FOO2 3)
   1: (BAZ 3)
   1: returned 3
   1: (BAR 3)
   1: returned 3
 0: returned 3
3
\end{code}

 \caption{Ambiguous tracing in Lisp.}
 \label{ambig}

\horizline
\end{figure}

\begin{figure}
\horizline

\begin{evaltrace}
+--> ;(foo1 3)
|
+**> ;Apply FOO1 to 3
*  +--> ;(bar (baz x))
*  |  +--> ;(baz x)
*  |  |
*  |  +**> ;Apply BAZ to 3
*  |  *
*  |  +_*> ;Result of BAZ is 3
*  +**> ;Apply BAR to 3
*  *
*  +_*> ;Result of BAR is 3
+_*> ;Result of FOO1 is 3
\strut
+--> ;(foo2 3)
|
+**> ;Apply FOO2 to 3
*  +--> ;(baz x)
*  |
*  +**> ;Apply BAZ to 3
*  *
*  +_*> ;Result of BAZ is 3
*  +--> ;(bar x)
*  |
*  +**> ;Apply BAR to 3
*  *
*  +_*> ;Result of BAR is 3
+_*> ;Result of FOO2 is 3
\end{evaltrace}

 \caption{Unambiguous tracing using evaltrace.}
 \label{eval}

\horizline
\end{figure}

Another notation for explaining some aspects of Lisp evaluation is the
``fence'' notation of Winston and Horn \cite{WinstonHorn89}.  Fence
notation focuses on the static structure of lexical contours; it is not
concerned with the dynamic process of evaluation, function invocation, and
return.  While it can represent the environment of a closure as a series of
nested fences, it cannot represent the application of closures, nor does it
cover macro expansion.  Like most Lisp TRACE notations, fence notation has
no way to represent the difference between FOO1 and FOO2 above.

We believe evaltrace notation offers a significant improvement over both
earlier notations, in terms of scope of coverage, graphical intuitiveness, and
extensibility.  Its generality also makes it useful for describing the
operational semantics of programming languages, and in such a way that program
traces can be given as ``two-dimensional'' diagrams.  In this respect,
evaltrace can be viewed as a pleasant alternative notation for Plotkin's
structured operational semantics~\cite{PlotkinSemantics}\@.  This connection
to the Plotkin-style semantics is discussed in~\cite{TouretzkyLee-forthcoming},
along with extensions to evaltrace for tail-recursion elimination, first-class
continuations, assignment, and multiple closures with a shared parent contour.

We hope that both Lisp novices and educators find the notation to be
as useful as we have.  In support of this, we have made available a
set of \LaTeX\ macros and a special font for producing evaltrace
diagrams similar to the ones in this paper.  They are available via
anonymous ftp in compressed tar format, from {\tt a.ergo.cs.cmu.edu}
(128.2.250.219), in directory {\tt pub/evaltrace}, files {\tt README}
and {\tt evaltrace.tar.Z}.  The appendix gives a brief guide on the
use of these macros and font.

\vskip 15pt

\paragraph{Acknowledgements.}

The authors would like to thank Robert Harper for pointing out the connection
between evaltrace notation and Plotkin's structured operational semantics.

\newpage

\begin{thebibliography}{99}

\bibitem{GabrielHistory} Gabriel, R. P. (1987) Lisp.  In S. C. Shapiro
(ed.), {\it Encyclopedia of Artificial Intelligence}, vol.~1, 508--528.  New
York: John Wiley.

\bibitem{PlotkinSemantics} Plotkin, G. (1981).
{\it A Structural Approach to Operational Semantics}.
Technical Report~DAIMI--FN--19, Computer Science Department, Aarhus
University, Denmark.
 
\bibitem{R3Scheme} Rees, J., and Clinger, W. (eds). (1986) The revised$^3$
report on the algorithmic language Scheme.  {\it ACM SIGPLAN Notices},
vol.~21, no.~12, 37--79.

\bibitem{CLtL} Steele, G. L. Jr. (1984) {\it Common Lisp: the Language.}
Burlington, MA:  Digital Press.

\bibitem{TouretzkyLisp} Touretzky, D. S. (1990) {\it Common Lisp:  A Gentle
Introduction to Symbolic Computation.}  Redwood City, CA:  Benjamin/Cummings.

\bibitem{TouretzkyLee-forthcoming} Touretzky, D. S., and Lee, P. (in
preparation) A graphical representation for evaluation and scoping in
applicative languages.

\bibitem{WinstonHorn89} Winston, P. H., and Horn, B. K. P. (1989) {\it LISP},
3rd edition.  Reading, MA:  Addison-Wesley.

\end{thebibliography}

\newpage

\appendix
\newcommand{\metafont}{{\small METAFONT}}
\input{../doc/docbody}

\end{document}
